The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for providing an atomic commit operation predicated on the consistency of watches.
An atomic operation is a set of two or more operations that can be combined so that they appear to the data processing system in which they are performed to be a single operation with only two possible outcomes: success or failure. With an atomic operation, operations in other sets of operations do not know about any changes being made by the operations within the set of operations that comprise the atomic operation until the entire set of operations completes. Moreover, with an atomic operation, if any of the operations within the set of operations fails, the entire set of operations fails and the state of the system is restored to the state it was in before any of the operations within the set of operations began executing.
An atomic commit is an operation which a set of distinct changes is applied as a single operation. If all the changes are applied, the atomic commit is said to have succeeded. If there is a failure before the atomic commit can be completed, the “commit” is aborted and all changes that have taken place are reversed or rolled back. In either case, the atomic commit leaves the system in a consistent state. Atomic commits are often used in database systems when committing multiple sets of changes at once. Atomic commits are employed by revision control systems whereby atomic commits are used to control uploading of changes of multiple files to a source of the files while guaranteeing that all files get fully uploaded and merged. Atomic commits are also employed by numerous transactional processing systems (ATMs, online purchasing, etc.) in which operations on different systems (e.g., order placement, credit card transaction, inventory update) are combined in a single set that succeeds or fails as a group.
Atomic commits are also useful in the areas of transactional memory and speculative multi-threading, also known as thread-level speculation. Transactional memory attempts to simplify concurrent or parallel programming by allowing a group of load and store instructions to execute in an atomic manner, i.e. it is guaranteed that either (1) all instructions of the transaction complete successfully or (2) no effects of the instructions of the transactions occur. With atomic transactions, the instructions of the transaction appear to occur all at once between invocation and results being generated.
Hardware transactional memory systems may have modifications to the processors, caches, and bus protocols to support transactions or transaction blocks, i.e. groups of instructions that are to be executed atomically as one unit. Software transactional memory provides transactional memory semantics in a software runtime library. Software transactional memory can be combined with hardware support to design a hybrid transactional memory system.
The concept of transactional memory was introduced by Herlihy and Moss “Transactional Memory: Architectural Support for Lock-Free Data Structures,” Proceedings of the 20th Annual International Symposium on Computer Architecture, pp. 289-300, May 1993. However, as described in Bobba et al., “Performance Pathologies in Hardware Transactional Memory,” ISCA '07, Jun. 9-13, 2007, a programmer can invoke a transaction in a multi-threaded application and rely on the transactional memory system to make its execution appear atomic in a global serial order. Bobba et. al discusses conflict resolution policies in transactional memory systems.
Transactional memory systems seek high performance by speculatively executing transactions concurrently and only committing transactions that are non-conflicting. A conflict occurs when two or more concurrent transactions access the same data element, e.g. a word, block, object, etc., and at least one access is a write. Transactional memory systems may resolve some conflicts by stalling one or more transactions.
Speculative multi-threading (SMT) is a type of speculative execution that occurs at a thread level as opposed to an instruction level. SMT is a dynamic parallelization technique that uses out-of-order execution of instructions of multiple threads to achieve an increase is operational speed of processors. With SMT, the changes performed by threads may be committed atomically if there are no dependency violations between threads. Dedicated hardware keeps track of speculative thread read (load) and write (store) data locations and aborts, i.e. rolls back or squashes, threads that are shown to have violated an actual data dependency.
Architectural support for atomically committing a set of stores is useful in mechanisms that employ coarse-grained speculation, such as transactional memory and thread level speculation or speculative multi-threading. However, such atomic support is complicated by two factors. First, it is challenging for hardware to support atomic commit of an unbounded number of stores. Second, in many contexts, this atomic commit needs to be predicated on whether there have been external writes (writes outside the set of instructions comprising the atomic block) to a, possibly different, set of blocks.